/*
02-线性结构3 Reversing Linked List
*/
#include <stdio.h>
#include <stdlib.h>

#define N 1000000
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    int address;
    ElementType data;
    int nextAddress;
    PtrToNode next;
};

// 读取一个节点
// void readOneNode(PtrToNode node) {
//     scanf("%d %d %d", &(node->address), &node->data, &node->nextAddress);
// }

// 按address在数组中查找节点
PtrToNode findByAddrss(PtrToNode nodes, int n, int address) {
    for (int i=0; i<n; i++) {
        if (address == nodes[i].address) {
            return &nodes[i];
        }
    }
    return NULL;
}

void printNode(PtrToNode pnode) {
    if (pnode->nextAddress == -1) {
        printf("%05d %d %d\n", pnode->address, pnode->data, pnode->nextAddress);
    } else {
        printf("%05d %d %05d\n", pnode->address, pnode->data, pnode->nextAddress);
    }
}

// 输出节点数组
void printNodeArray(PtrToNode nodes, int n) {
    PtrToNode p = nodes;
    for (int i=0; i<n; i++, p++) {
        printNode(&nodes[i]);
    }
}

// 从输入读取链表
PtrToNode readList(int firstAddr, int *n) {
    int m = *n;
    // 先读取到一个数组中
    PtrToNode nodes = (PtrToNode) malloc(sizeof(struct Node)*N);
    for (int i=0; i < m; i++) {
        int a;
        scanf("%d", &a);
        nodes[a].address = a;
        scanf("%d %d", &nodes[a].data, &nodes[a].nextAddress);
        // printNode(&nodes[a]);
    }
    
    // 把节点按次序放入数组中
    PtrToNode newNodes = (PtrToNode) malloc(sizeof(struct Node)*(*n));
    newNodes[0] = nodes[firstAddr];
    for (m=1; m<*n && newNodes[m-1].nextAddress!=-1; m++) {
        newNodes[m] = nodes[newNodes[m-1].nextAddress];
        // head = head->next;
    }
    *n = m;
    free(nodes);
    return newNodes;
}

void updateNextAddress(PtrToNode nodes, int n) {
    for (int i=1; i<n; i++) {
        nodes[i-1].nextAddress = nodes[i].address;
    }
    nodes[n-1].nextAddress = -1;
}

void reverseSub(PtrToNode nodes, int s, int e) {
    // printf("s=%d, e=%d\n", s, e);
    for (int i=s, j=e; i<j; i++, j--) {
        // printf("swap %d - %d\n", i, j);
        struct Node t = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = t;
    }
}

void reverse(PtrToNode nodes, int n, int k) {
    // 反转
    int m = n/k;// + (n%k==0 ? 0 : 1);
    for (int i=0; i < m; i++) {
        reverseSub(nodes, i*k, (i+1)*k-1);
    }
    updateNextAddress(nodes, n);
}

int main() {
    int firstAddr;
    int n, k;
    PtrToNode nodes;
    scanf("%d %d %d", &firstAddr, &n, &k);
    // printf("%d, %d\n", n, k);
    nodes = readList(firstAddr, &n);
    // printNodeArray(nodes, n);
    
    reverse(nodes, n, k);
    printNodeArray(nodes, n);
    free(nodes);
    return 0;
}
